package leetcode.code0073;

public class Solution extends Solution73 {

	@Override
	public void setZeroes(int[][] matrix) {
		int row = matrix.length;
		int col = matrix[0].length;
		boolean rowOne = false;// 第0行需要变成0吗
		for (int i = 0; i < col; i++) {
			if (matrix[0][i] == 0) {
				rowOne = true;
				break;
			}
		}
		boolean colOne = false;// 第0列需要变成0吗
		for (int i = 0; i < row; i++) {
			if (matrix[i][0] == 0) {
				colOne = true;
				break;
			}
		}
		// 除了第0行和第0列，所有的0都标记在相应的第0行和第0列
		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				if (matrix[i][j] == 0) {
					matrix[i][0] = 0;
					matrix[0][j] = 0;
				}
			}
		}
		// 除了第0列，遍历第一行，把所有列标记为0的列，当前列都变成0
		for (int i = 1; i < col; i++) {
			if (matrix[0][i] == 0) {
				for (int j = 1; j < row; j++) {
					matrix[j][i] = 0;
				}
			}
		}
		// 类似，变行
		for (int i = 1; i < row; i++) {
			if (matrix[i][0] == 0) {
				for (int j = 1; j < col; j++) {
					matrix[i][j] = 0;
				}
			}
		}
		// 最后决定0行是否变成0
		if (rowOne) {
			for (int i = 0; i < col; i++) {
				matrix[0][i] = 0;
			}
		}
		// 最后决定0列是否变成0
		if (colOne) {
			for (int i = 0; i < row; i++) {
				matrix[i][0] = 0;
			}
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
	}

}
